/*包含头文件*/
#include <stdio.h>
#define MAXSIZE 60
/*函数声明*/
void Hanoi1(int n, char a, char b, char c);
void Hanoi2(int n, char a, char b, char c);
void PrintHanoi(int no, char from, char to);

typedef struct
{
    char a,b,c;
    int flag,num;
}stack;

int main()
{
    int n;
    printf("请输入移动圆盘的个数:\n");
    scanf("%d",&n);
    printf("汉诺塔的递归实现:\n");
    Hanoi1(n,'a','b','c');
    printf("汉诺塔的非递归实现:\n");
    Hanoi2(n,'a','b','c');
    return 0;
}

void PrintHanoi(int no, char from, char to)//输出汉诺塔的圆盘移动过程
{
    printf("将第%d个圆盘从%c移动到%c\n",no,from,to);
}

void Hanoi1(int n, char a, char b, char c)
{
    if (n==1) PrintHanoi(n,a,c);
    else
    {
        Hanoi1(n-1,a,c,b);
        PrintHanoi(n,a,c);
        Hanoi1(n-1,b,a,c);
    }
}

void Hanoi2(int n, char a, char b, char c)
{
    int top=1,a1,b1,c1,m;
    stack s[MAXSIZE];
    //初值入栈
    s[top].num=n;
    s[top].flag=1;
    s[top].a=a;
    s[top].b=b;
    s[top].c=c;
    while(top>0)
    {
        if (s[top].flag==1)
        {
            //退栈hanoi(n,a,b,c),相当于在递归函数中将实参传给形参
            m=s[top].num;
            a1=s[top].a;
            b1=s[top].b;
            c1=s[top].c;
            top--;
            /*将hanoi(n-1,a,b,c)入栈,相当于在递归函数中的第一个递归调用函数,
              将编号为1~n-1的圆盘从塔座a移动到b,c作为辅助塔座*/
            top++;
            s[top].num=m-1;
            s[top].flag=1;
            s[top].a=b1;
            s[top].b=a1;
            s[top].c=c1;
            //将第n个圆盘从a移动到c
            top++;
            s[top].num=m;
            s[top].flag=0;
            s[top].a=a1;
            s[top].c=c1;
            /*将hanoi(n-1,b,a,c)入栈,相当于在递归函数中的第一个递归调用函数,
              将编号为1~n-1的圆盘从塔座b移动到c,a作为辅助塔座*/
            top++;
            s[top].num=m-1;
            s[top].flag=1;
            s[top].a=a1;
            s[top].b=c1;
            s[top].c=b1;
        }
        while(top>0&&(s[top].flag==0||s[top].num==1))
        {
            if(top>0)//将第n个圆盘从a移动到c,并退栈
            {
                PrintHanoi(s[top].num,s[top].a,s[top].c);
                top--;
            }
        }
    }
}

